A pseudo-random number generator is one of the most extensively used computer functions. It is included in the standard libraries of almost all programming languages. A random number generator might be called several million times during one run of a large simulation process.
One prior art method of random number generation is described in Lewis P A W, Goodman A S, and Miller J M "A Pseudo-Random Number Generator for the System/360", IBM System J., 8, pp 136-146, (1969) [1].
The generator described in [1] is based on the following recursion formula: EQU X.sub.i+1 =A X.sub.i (mod P). (1)
where A is a positive primitive root of prime P, and the starting seed X.sub.0 may be any number between 1 and P-1 inclusive. This method will generate all the values between 1 and P-1 in some order with no repetition.
The larger P is, the longer is the period of generated random numbers. Usually the largest prime number representable in one machine word is selected for random number generation. On a 32-bit machine it is 2.sup.31 -1, and almost all generators on such machines use it.
This method is known as the linear congruential generation method. Implementation of a random number generator function according to this method requires only two instructions, one multiply instruction and one divide instruction.
However, while multiplication on modern computers may be done in one machine cycle, division is relatively slow, and usually requires several cycles.